package com.yang.Offer;

public class Offer13 {
}

// 机器人的运动范围
class Offer13Solution {
    int m;
    int n;
    int k;
    boolean[][] visited;
    // m n 表示方格大小
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        visited = new boolean[m][n];
        return dfs(0, 0);
    }
    private int dfs(int i, int j){
        // 如果没有满足  没有移动到方格外，且满足数位和，且该方格机器人没有来过 这些条件
        if(j < 0 || i < 0 || i >= m || j>= n || visited[i][j] || (sum(i)+sum(j)) > k ){
            return 0;
        }
        // 否则满足条件
        visited[i][j] = true;
        // 机器人向四面搜索  根据规律
        // (官方的 不嫌麻烦可以自己计算 就是说它在前进的过程中只需要向下向右就循环完每个能走的路径而中间是不会出现需要向上向左的障碍)
        return 1 + dfs(i + 1, j)  + dfs(i, j + 1);
    }

    // 计算位数和
    private int sum(int x){
        int sum = 0;
        while (x != 0){
            sum = sum + x%10;
            x /= 10;
        }
        return sum;
    }
}
